package monotonous_queue;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 算法：单调栈、双指针
 * 只有递减再升高的顺序才能接到雨水, 这样才能形成凹槽接雨水
 * 如果当前元素比栈顶元素还大，栈顶元素出栈，
 * 如果出栈的元素比新栈顶元素还小，那么可以接到雨水
 * 反之，入栈，因为后面可能还有比目前栈顶元素还大的值，这样可以接到雨水
 * 本质: 在左右两边找到第一次比当前柱子高的柱子
 *
 * @author yzh
 * @version 1.0
 * @date 2021/11/3 9:11
 */
public class _42 {
    public static void main(String[] args) {
//        System.out.println(new _42().trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(new _42().trap(new int[]{4, 2, 0, 3, 2, 5}));
    }

    public int trap(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int cur = stack.pop();
                if (stack.isEmpty()) break;
                int l = stack.peek();
                int h = Math.min(height[i], height[l]) - height[cur];
                ans += (i - l - 1) * h;
            }
            stack.push(i);
        }
        return ans;
    }

    int trap_double_point(int[] height) {
        int ans = 0, l = 0, r = height.length - 1;
        int lMax = height[l], rMax = height[r];
        while (l < r) {
            lMax = Math.max(lMax, height[l]);
            rMax = Math.max(rMax, height[r]);
            if (lMax < rMax) {
                ans += lMax - height[l];
                ++l;
            } else {
                ans += rMax - height[r];
                --r;
            }
        }
        return ans;
    }

}
